package main

import "fmt"

//你也许会说，找到一个 target，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。
//这道题目并没有使用边界二分查找
//https://labuladong.github.io/algo/2/18/26/

func searchRange(nums []int, target int) []int {
	left, right := 0, len(nums)
	if 0 == right {
		return []int{-1, -1}
	}

	var mid int
	begin, end := -1, -1
	for {
		mid = left + (right-left)/2
		if nums[mid] == target {
			//向后探索
			for index := 1; ; {
				if mid+index == len(nums) || nums[mid+index] != target {
					end = mid + index - 1
					break
				}
				index++
			}
			//向前探索
			for index := 1; ; {
				if mid == index-1 || nums[mid-index] != target {
					begin = mid - index + 1
					break
				}
				index++
			}
			return []int{begin, end}
		} else if nums[mid] > target {
			if right == mid {
				break
			}
			right = mid
		} else if nums[mid] < target {
			if left == mid {
				break
			}
			left = mid
		}
	}
	return []int{begin, end}
}
func main() {
	//nums := []int{1}
	//fmt.Println(len(nums))
	nums := []int{5, 7, 7, 8, 8, 10}
	target := 8
	fmt.Println(searchRange(nums, target))
}
